package list;
//环形链表
public class leetcode141 {
    public static void main(String[] args) {
        int[] nums = {-21,10,17,8,4,26,5,35,33,-7,-16,27,-12,6,29,-12,5,9,20,14,14,2,13,-24,21,23,-21,5};
        int pos = -1;
        ListNode head = createList(nums, pos);
        printList(head, nums);
        System.out.println(hasCycle(head));
    }

    public static ListNode createList(int[] nums, int pos){
        ListNode head = new ListNode(nums[0]);
        ListNode temp = head;

        for (int i = 1; i < nums.length; i++) {
            ListNode cur = new ListNode(nums[i]);
            cur.next = null;
            temp.next = cur;
            temp = temp.next;
        }

        ListNode cur = head;

        while(pos >= 0){
            if(pos == 0)
                temp.next = cur;
            pos--;
            cur = cur.next;
        }

        return head;
    }

    public static void printList(ListNode head, int[] nums) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        if(head != null){
            System.out.print(head.val + "-> ...");
        }
        else{
            System.out.println("null");
        }
    }

    public static boolean hasCycle(ListNode head){
        if(head == null) return false;
        ListNode slow = head;
        ListNode fast = head;
        if(head.next == null) return false;
        while (fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) return true;
        }
        return false;
    }

    public boolean hasCycle2(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) return false;
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}
